/* s2 - perfect hash table lookups
   Copyright (C) 2019 Ariadne Devos

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

#ifndef _sHT_PHASH_H
#define _sHT_PHASH_H

#include <stddef.h>
#include <stdint.h>

/** Perfect hash tables

  Hash tables are a particular technique for mapping keywords to their
  associated value. When the keyword set is static, s2 prefers to generate
  the hash table at compile-time. For this, gperf[GPERF] is used, which has
  a few appealing properties:

  - it does not allocate memory at run-time
  - the code size is quite reasonable
  - O(1) worst-case performance
  - nice syntax for specifying the mapping

  [GPERF]: GPERF A Perfect Hash Function Generator, Douglas C. Schmidt
  (apparently 1998), http://www.cse.wustl.edu:80/~schmidt/PDF/gperf.pdf)
  (currently hosted at https://gnu.org/software/gperf)

  This module consists of a run-time API and a compile-time bash script.
  The table will map strings to 32-bit integers. Empty entries are
  initialised to zero.

  At run-time, use the generated lookup function. It has the same API
  as @var{sHT_perfect_lookup}, except that @var{table} and @var{hash}
  do not have to be passed.

  At compile-time, use the buffer/gen-phash.sh script. */

struct sHT_perfect_entry;
struct sHT_perfect_table;

struct sHT_perfect_entry
{
        uint_least16_t name;
        uint_least16_t length;
        uint_least32_t value;
};

struct sHT_perfect_table
{
	const struct sHT_perfect_entry *values;
	/* also 1+ the maximum hash
	   TODO: on x86-64, there are enough free bits in
	   @var{string_pool} and @var{values} -- save some
	   memory?  */
	uint_least16_t values_length;
	/* TODO: make this a flexible array member, saving a pointer */
	const unsigned char *string_pool;
};

/** From a string key and its hash, find its value in the hash table

  All first n characters of @var{string} may be accessed,
  where n is the length of the largest key in @var{table}
  -- these may all leak through side channels.

  Return its value in @var{table}, or 0 if there is no such entry.
  On a speculative execution, an incorrect value may be returned:
  0 or any of @var{table}'s values. */
size_t
sHT_perfect_lookup(const struct sHT_perfect_table *table, const uint8_t string[], size_t length, size_t hash);

#endif
